#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAXN = 1E5+7;
vector<int> M[MAXN];
int vis[MAXN];
int dep[MAXN];
bool hasPrime;
void DFS(int r, int pre, int& cnt) {
    ++cnt;
    vector<int> &vec = M[r];
    int len = vec.size();
    for (int i=0; i<len; ++i) {
        int t = vec[i];
        if (vis[t] == 0) {
            vis[t] = 1;
            dep[t] = dep[r] + 1;
            DFS(t, r, cnt);
            vis[t] = 2;
        }
        else if (t != pre && vis[t] == 1) {
            if ((dep[r] - dep[t]) % 2 == 0) {
                hasPrime = true;
            }
        }
    }
}
void myDFS(int n, int& maxLink) {
    maxLink = 0;
    hasPrime = false;
    memset(vis, 0, sizeof(vis));
    memset(dep, 0, sizeof(dep));
    for (int i=1; i<=n; ++i) {
        if (vis[i]==0) {
            int cnt = 0;
            vis[i] = 1;
            DFS(i, -1, cnt);
            vis[i] = 2;
            if (cnt > maxLink) maxLink = cnt;
        }
    }
}

int main() {
    int n,m;
    scanf("%d %d", &n, &m);
    int s,e;
    for (int i=0; i<m; ++i) {
        scanf("%d %d", &s, &e);
        M[s].push_back(e);
        M[e].push_back(s);
    }
    int ml;
    myDFS(n, ml);
    if (ml == 0) printf("0\n");
    else if (ml == 1) printf("1\n");
    else {
        if (hasPrime) printf("3\n");
        else printf("2\n");
    }
    return 0;
}
